
export function getHashCode(str: string, max: number): number {
    // 最好为质数
    let hashCode: number = 0
    for (let i = 0; i < str.length; i++) {

        hashCode = 31 * hashCode + str.charCodeAt(i)
    }
    return hashCode % max
}
export function isPrime(num: number) {

    let sqrt = parseInt(Math.sqrt(num).toString())
    for (var i = 2; i <= sqrt; i++) {
        debugger
        if (num % i === 0) {
            return false
        }
    }

    return true
}

const MAXVALUE = 0.75
class HashTable {
    private storge: any[][]
    private count: number
    private limit: number
    constructor() {
        this.storge = [] // 元素集合
        this.count = 0 // 实际个数
        this.limit = 7// 总个数
    }

    // 哈希函数
    getHashCode(key: string, max: number): number {
        return getHashCode(key, max)
    }

    /**
     * 
     * @param key 
     * @returns hashkey
     */
    private getIndex(key: string) {
        return this.getHashCode(key, this.limit)
    }

    /**
     * 
     * @param num 质数
     * @returns 
     */
    private getPrime(num: number) {
        while (!isPrime(num)) {
            num++
        }
        return num
    }

    // 放入元素 hashMap =>{key:value}
    put(key: string, value: any) {
        const index = this.getIndex(key)
        let bucket = this.storge[index]
        if (bucket === undefined) {
            bucket = []
            this.storge[index] = bucket
        }
        let override: boolean = false
        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i][0] === key) {
                bucket[i][1] = value
                override = true
                break
            }
        }
        if (!override) {
            this.storge[index].push([key, value])
            this.count++

            if (this.count > MAXVALUE * this.limit) {
                debugger
                var num = this.getPrime(this.limit * 2)
                this.resize(num)
            }
        }

    }

    /** 
     * 删除一个键值
     * @param key 
     */
    remove(key: string): boolean {
        const index = this.getIndex(key)
        const bucket = this.storge[index]
        if (!bucket) {
            return false
        }
        for (let i = 0; i < bucket.length; i++) {

            if (bucket[i][0] === key) {
                bucket.splice(i, 1)
                this.count--
                if (this.count > 8 && this.count < MAXVALUE * this.limit) {
                    this.resize(this.getPrime(Math.floor(this.limit / 2)))
                }
                return true
            }
        }
        return false
    }

    /**
     * 获取元素
     * @param key 
     */
    get(key: string): string | null {
        const index = this.getIndex(key)
        const bucket = this.storge[index]
        if (!bucket) {
            return null
        }
        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i][0] === key) {
                return bucket[i][1]
            }
        }
        return null
    }

    size() {
        return this.count
    }

    isEmpty() {
        return this.count === 0
    }

    resize(newlimit: number) {
        let oldstorge = this.storge.slice()
        this.limit = newlimit
        this.storge = []
        this.count = 0
        for (let i = 0; i < oldstorge.length; i++) {
            if (oldstorge[i]) {
                oldstorge[i].forEach(e => {
                    this.put(e[0], e[1])
                })
            }
        }
    }

}

export { HashTable }